package com.test.daily.leetcode.y2022.m07.day0722.v01;
import java.util.ArrayDeque;
import java.util.HashSet;
import java.util.Queue;
import java.util.Set;
/**
 * @author Tom on 2022/7/22
 */
public class Solution {
    public boolean sequenceReconstruction(int[] nums, int[][] sequences){
        int N = nums.length;
        Set<Integer>[] sets = new Set[N+1];
        for (int i = 0; i < N+1; i++) {
            sets[i] = new HashSet<>();
        }
        int[] indegre = new int[N+1];
        for(int[] sequence: sequences){
            int len = sequence.length;
            for (int i = 1; i < len; i++) {
                int pre = sequence[i] -1, next = sequence[i];
                if(sets[pre].add(next)){
                    indegre[next]++;
                }
            }
        }
        Queue<Integer> queue = new ArrayDeque<>();
        for (int i = 0; i <= N; i++) {
            if(indegre[i] == 0){
                queue.add(i);
            }
        }
        while(!queue.isEmpty()){
            if(queue.size() > 1){
                return false;
            }
            int i = queue.poll();
            for(int next: sets[i]){
                indegre[next]--;
                sets[i].remove(next);
                if(indegre[next] == 0){
                    queue.add(next);
                }
            }
        }
        return true;
    }
}
